package com.dyz.LeetCodeforSwordFingerOffer;

public class Exist12 {
    //回溯算法
    public boolean exist(char[][] board, String word) {
        if (board==null||board.length==0||board[0]==null||board[0].length==0||word==null){
            return false;
        }
        int n = board.length;
        int m = board[0].length;
        boolean [][] isVisited = new boolean[n][m];
        //遍历 两层for循环
        for(int i = 0; i< board.length;i++){
            for(int j =0 ; j<board[0].length;j++){
                if(dfs(board, word,i, j, isVisited, 0)){return true;}
            }
        }
        return false;

    }

    private boolean dfs(char[][] board, String word, int i, int j,boolean [][] isVisited, int n){
        //终止条件
        if(i<0||i>=board.length||j<0||j>=board[0].length||isVisited[i][j]){ // isVisited[i][j] 已经访问过了
            return false;
        }
        //终止条件2
        //当前位置和我们需要的字符word.charAt(n)不同，该路径行不通
        if(board[i][j]!=word.charAt(n)){//这个就是回溯的选择条件
            return false;
        }
        //终止条件3
        //我们要查找的最后一个字符都通过了上面那条if语句，该单词路径存在
        if(n==word.length()-1){
            return true;
        }

        //标记已经访问过了
        isVisited[i][j] = true;

        //上面条件不满住， 四个方向上下左右
        boolean flag = dfs(board, word,i+1,j, isVisited, n+1)||
                dfs(board, word,i-1,j, isVisited, n+1) ||
                dfs(board, word,i,j+1, isVisited, n+1) ||
                dfs(board, word,i,j-1, isVisited, n+1);

        isVisited[i][j] = false;//状态回退
        return flag;
    }
}
